// InsertionSort.cpp
#include <vector>
#include <iostream>

using namespace std;

/*
 * [8]
 *
 *     i=1  2  3  4  5 索引
 * [8, 5, 2, 9, 6, 3] 
 *     ^右手
 * [8, 5] 左手
 *     ^j
 * 牌 5 来说，他有两个可能插入的位置，分别是 1 和 0 
 * 我们要比较的是，位置 j 和位置 j 的前一个位置的牌面
 */
vector<int> insertionSort(vector<int> array) {
  for (int i = 1; i < array.size(); ++i) {
    // 摸牌的过程
    for (int j = i; j > 0; --j) {
      if (array[j] < array[j - 1]) {
        swap(array[j], array[j - 1]);
      }
    }
  }

  return array;
}

int main(int argc, char const *argv[])
{
  /* code */
  /* code */
  vector<int> array {4, 1, 5, 9, 6};
  array = insertionSort(array);

  for (int n : array) {
    cout<<n<<" ";
  }

  cout<<endl;
  return 0;
}
